#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <Vector.hpp>

using namespace std;

class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        vector<int> result;
        map<string, int> refer_map;
        for (string word : words)
        {
            refer_map[word]++;
        }
        int word_len = words[0].length();
        for (int offset = 0; offset < word_len; offset++)
        {
            int word_cell = 0;
            int amount = 0;
            map<string, int> word_map;
            while (offset + word_cell * word_len + word_len <= s.length())
            {
                if (amount < words.size())
                {
                    // add new
                    string word = s.substr(offset + word_cell * word_len, word_len);
                    word_map[word]++;
                    amount++;
                }
                else
                {
                    // remove old add new
                    string new_word = s.substr(offset + word_cell * word_len, word_len);
                    word_map[new_word]++;
                    string old_word = s.substr(offset + (word_cell - words.size()) * word_len, word_len);
                    if (word_map[old_word] == 1)
                    {
                        word_map.erase(old_word);
                    }
                    else
                    {
                        word_map[old_word]--;
                    }
                }
                if (amount == words.size())
                {
                    // check if valid
                    if (word_map == refer_map)
                    {
                        result.push_back(offset + (word_cell - words.size() + 1) * word_len);
                    }
                }
                word_cell++;
            }
        }
        return result;
    }
};

int main()
{
    cout << "Code30" << endl;
    Solution s;
    string ss = "barfoothefoobarman";
    vector<string> words{"foo", "bar"};
    vector<int> result = s.findSubstring(ss, words);
    PrintVector(result);
    return 0;
}